#include <iostream>
#include <vector>
#include <functional>
using namespace std;

function<void(vector<int> &)> output = [](vector<int> &arr) -> void
{
    int length = arr.size();
    for (int i = 0; i < length; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
};

void insertSort_1(vector<int> &arr)
{
    int length = arr.size();
    for (int i = 1; i < length; ++i)
    {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; --j)
        {
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
        }
    }
}

void insertSort_2(vector<int> &arr)
{
    int length = arr.size();
    for (int i = 1; i < length; ++i)
    {
        int num = arr[i];
        int j = i - 1;
        for (; j >= 0 && arr[j] > num; --j)
        {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = num;
    }
}

void insertSort_2_2(vector<int> &arr)
{
    int length = arr.size();
    for (int i = 1; i < length; ++i)
    {
        int num = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > num)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = num;
    }
}

int main()
{
    vector<int> arr = {6, 2, 1, 3, 5, 4, 9, 7, 5, 4, 11};

    vector<int> temp(arr);
    output(temp);
    insertSort_1(temp);
    output(temp);
    temp = arr;
    output(temp);
    insertSort_2(temp);
    output(temp);
    temp = arr;
    output(temp);
    insertSort_2_2(temp);
    output(temp);
    return 0;
}
